#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 边的数据结构
struct Edge {
	int u, v, weight;
	bool operator<(const Edge& other) const {
		return weight < other.weight;
	}
};

// 并查集的数据结构
class UnionFind {
	private:
		vector<int> parent;
	public:
		UnionFind(int size) : parent(size) {
			for (int i = 0; i < size; ++i) {
				parent[i] = i;
			}
		}

		int find(int x) {
			if (parent[x] != x) {
				parent[x] = find(parent[x]); // 路径压缩
			}
			return parent[x];
		}

		void unite(int x, int y) {
			int rootX = find(x);
			int rootY = find(y);
			if (rootX != rootY) {
				parent[rootX] = rootY; // 合并两个集合
			}
		}

		bool connected(int x, int y) {
			return find(x) == find(y);
		}
};

// Kruskal算法实现
pair<vector<Edge>, int> kruskal(vector<Edge>& edges, int n) {

	sort(edges.begin(), edges.end()); // 按照权重排序

	UnionFind uf(n);
	vector<Edge> mst;
	int mstWeight = 0;
cout << uf.connected(1, 2) << "!!!!\n";
	for (Edge& edge : edges) {
		if (!uf.connected(edge.u, edge.v)) { // 如果不会形成环
			uf.unite(edge.u, edge.v); // 合并两个集合
			mst.push_back(edge); // 添加到MST
			mstWeight += edge.weight; // 更新MST的权重
		}
	}

	return {mst, mstWeight};
}

int main() {
	int n, e;
	vector<Edge> edges;

	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		edges.push_back({x - 1, y - 1, z});
	}

	auto [mst, totalWeight] = kruskal(edges, n);

	for (Edge e : mst) {
		cout << e.u + 1 << "  " << e.v + 1 << endl;
	}
	cout << totalWeight << endl;

	return 0;
}
